package main

type UnionFind struct {
	parents map[byte]byte
}

func New() *UnionFind {
	return &UnionFind{
		parents: make(map[byte]byte),
	}
}

func (uf *UnionFind) Find(x byte) byte {
	origin := x
	for uf.parents[x] != x && uf.parents[x] != 0 {
		x = uf.parents[x]
	}
	uf.parents[origin] = x
	return x
}

func (uf *UnionFind) Union(x, y byte) {
	rootX := uf.Find(x)
	rootY := uf.Find(y)
	uf.parents[rootX] = rootY
}

func (uf *UnionFind) IsConnected(x, y byte) bool {
	rootX := uf.Find(x)
	rootY := uf.Find(y)
	return rootX == rootY
}

func equationsPossible(equations []string) bool {
	// 第一次遍历所有相等关系
	uf := New()
	for _, eq := range equations {
		if eq[1] == '=' {
			uf.Union(eq[0], eq[3])
		}
	}
	// 第二次遍历所有不等关系
	for _, eq := range equations {
		if eq[1] == '!' {
			if uf.IsConnected(eq[0], eq[3]) {
				return false
			}
		}
	}
	return true
}

func main() {
	eqs := []string{
		"a==b",
		"b==a",
		"c==a",
		"b!=c",
	}
	println(equationsPossible(eqs))
}
